COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Exercise - Dynamic Programming
C00016 00003	For section in Debugging
C00019 00004	Algorithms 2
C00037 ENDMK
C⊗;
Exercise - Dynamic Programming

Some positions that arise in the game of backgammon become simple races,
where the first player to roll a large enough cumulative total on the dice
wins the game.  A player rolls two dice; if the numbers on the dice are
different, the player gets the sum, but if the numbers are equal, he gets
twice the sum; 1 & 2 gives the player 3, while 6 & 6 gives him 24.  

Calculate the average number of turns required for a player to accumulate a
total of 100.  Warning: don't fall into the trap of dividing 100 by the
average roll (8 1/6).

Harder Exercise - Dynamic Programming

Calculate the winning chance of the player whose turn is next in a
backgammon race (see previous problem), if the first player needs a total
of 38, and the second a total of 40.

Hardest Exercise - Dynamic Programming (Suitable for term project)

In backgammon as played for money, at any one time one (or initially both)
of the players has the right to double the stakes before rolling the dice,
if he thinks that on the average he will win the most money by doing so. 
The opponent may either give up the game, paying the current stake, or
agree to let the game continue for twice the current stake, in which case
the first player proceeds with his dice roll.  When a player uses the right
to double, he loses it and the other player gets it, so doubling alternates
between the players.

In the situation of the previous problem, if the first player has doubled
earlier in the game, so that the current stake is 2 units,  on the average
what will be the first player's net winnings, counting losses as negative
winnings?  Assume that each player offers and accepts doubles to maximize
average net winnings.  To make the problem harder, assume that neither
player has doubled; find the first player's average winnings, and determine
whether he should double before his first roll of the dice.
For section in Debugging

Do you remember the dictionary search algorithm?  Look back at page    if
you don't (and why don't you have every word memorized?  If you appreciated
how hard I worked writing this book, you would study harder, you lazy
good-for-nothing!  Do your parents know that they spend $8000 a year so
that you can hang out at the Oasis, the Dutch Goose, and Zots?)  Well,
anyway, here is a Pascal algorithm for it, where DICT[I] is a string, the
I'th word in an N-word dictionary.

	READ(WORD);
	LEFT:=1;
	RIGHT:=N;
	MIDDLE:=(LEFT+RIGHT) DIV 2
	WHILE WORD <> DICT[MIDDLE] DO
		BEGIN
		IF WORD < DICT[MIDDLE] THEN
			RIGHT:=MIDDLE
		ELSE LEFT:=MIDDLE;
		MIDDLE:=(LEFT+RIGHT) DIV 2
		END;
	WRITE('WORD IS IN LOCATION', MIDDLE)

_EXERCISE_

The program above does not work.  Find what is wrong and repair it.  
(Hint: What if it is a two word dictionary?)
(Second Hint: What is the invariant supposed to be?)

_EXERCISE_

The program above is designed on the assumption that WORD is in the
dictionary.  Modify it so that it will announce that a word is not in the
dictionary. 
(Hint: Assume it is a two-word dictionary, containing `B' and `D'.  Make
sure it does what you want, whether WORD is `A', `B', `C', `D', or `E'.
Algorithms 2

Algorithms meant to be performed by humans can be expressed in any way that
the humans can understand.  Algorithms meant to be performed by computers
must be expressed in a language computers can interpret.  Most computers
are designed to interpret algorithms written in a very crude notation
("machine language") that most humans find unsatisfactory as a language in
which to express algorithms.  We meet the needs of both the human algorith
designer and the computer interpreting the algorithm by providing a
translation;  programmers write algorithms in a language designed for
convenience and expressiveness, the algorithm is translated (by another,
pre-existing computer program) into machine language, and the machine
language version of the algorithm is carried out by the computer.  The
programmer need not know anyghing about the machine language, little
programming is done in machine language.

Pascal is a language for writing algorithms, using a misture of English and
mathematical notation.  Programs written in Pascal can be translated, by
other programs called ←compilers← or ←translators←, into the machine
languages of most popular computers.  Because Pascal is a standard,
programs written in Pascal can be shared among the users of diverse
computers, and can continue to be used without change when obsolete
computers are replaced by newer ones.

Most Pascal translators accept programs in Pascal extended by notations to
make more efficient use of facilites peculiar to a particular computer.
Some translators actually accept programs written in dialects of Pascal.
The International Standards Organization (ISO) has formulated a definition
of Pascal, called Standard Pascal, which is widely accepted; normally,
programs in Standard Pascal can be expected to work with all translators of
recent design.  This text uses Standard Pascal almost almost exclusively;
departures to use computer capabilities not expressible in Pascal are
explicitly labeled non-standard.